# 1、分解
# 在R[low:high]中选定一个元素R[pivot]，以此为标准将要排序的序列划分为两个序列R[low:pivot-1]与R[pivot+1：high]，并使序列R[low:pivot-1]中所有元素的值小于等于R[pivot]，序列R[pivot+1：high]所有的值大于R[pivot]，此时基准元素以位于正确位置，它无需参加后续排序。
# 2、递归
# 对于子序列R[low:pivot-1]与R[pivot+1：high]，分别调用快速排序算法来进行排序。
# 3、合并
# 由于对序列R[low:pivot-1]与R[pivot+1：high]的排序是原地进行的，所以R[low:pivot-1]与R[pivot+1：high]都已经排好序后，不需要进行任何计算，就已经排好序。
def quicksort(alist,start,end):
    if start>=end:######start>=end,递归退出
        return
    mid=alist[start]#设定起始的基准元素
    low=start#设定low（从左往右移动的游标为开始元素
    high=end#设定high（从右往左移动的游标为最后元素
    while low<high:#如果low和high未重合，high指向的元素若大于等于基准元素，则游标向左移动一位
        while low<high and alist[high]>=mid:
            high-=1
        alist[low]=alist[high]#high的值比基准元素的值小，将high指向的元素放到low上，此时high指向的位置为空
        while low<high and alist[low]<mid:
            low+=1
        alist[high]=alist[low]#low的值比基准元素大，将low指向的元素放到high上，此时low指向的位置为空
#退出循环后，low与high重合，此时所指位置为基准元素正确位置
    alist[low]=mid#将基准元素放进正确位置
    quicksort(alist,start,low-1)#对基准元素左边的序列进行快速排序
    quicksort(alist,low+1,end)#对基准元素右边的子序列快速排序
#主函数
if __name__=="__main__":
    alist=[6,2,7,16,58,42,86,37]
    quicksort(alist,0,len(alist)-1)
    print(alist)
